///PHILOTES Source Code.  (C)2012 PhiloLabs
#pragma once

// The underlying algorithms in this class are based heavily on:
/*
 *  Progressive Mesh type Polygon Reduction Algorithm
 *  by Stan Melax (c) 1998
 */

#ifndef __ProgressiveMesh_H_
#define __ProgressiveMesh_H_

#include "OgrePrerequisites.h"
#include "math/vector3.h"
#include "math/vector2.h"
#include "OgreHardwareVertexBuffer.h"
#include "OgreHardwareIndexBuffer.h"
#include "OgreRenderOperation.h"
#include "OgreSmallVector.h"

namespace Ogre {

	
	
	class Mesh;
	class SubMesh;
	
	class _OgreExport BitArray
	{
	public:
		BitArray()					: bits_ptr(NULL) {}
		BitArray(int bits_count)	: bits_ptr(NULL) { resize(bits_count); }
		BitArray& operator=(const BitArray& ba)	{ bits = ba.bits; bits_ptr = bits.size() > 0 ? &bits.front() : NULL; return *this; }
		
		bool getBit(size_t i) const	{ return bits_ptr[i >> 3] & bit_mask[i & 7]; }
		void setBit(size_t i)		{ bits_ptr[i >> 3] |= bit_mask[i & 7]; }
		void clearBit(size_t i)		{ bits_ptr[i >> 3] &= ~bit_mask[i & 7]; }
		void clearAllBits()			{ memset(bits_ptr, 0, bits.size()); }
		
		bool empty() const			{ return bits.empty(); }
		void resize(size_t bits_count)
		{		
			bits.resize((bits_count + 7) / 8);
			bits_ptr = bits.size() > 0 ? &bits.front() : NULL;
			clearAllBits();
		}
		
		size_t getBitsCount() const
		{
			size_t count = 0;
			for(unsigned char *ptr = bits_ptr, *end_ptr = bits_ptr + bits.size(); ptr != end_ptr; ++ptr)
			{
				const unsigned char b = *ptr;
				count += bit_count[b & 0xF] + bit_count[b >> 4];
			}
			return count;
		}
		
	private:
		unsigned char*				bits_ptr;		// it`s so performance critical, so we place raw data pointer before all other members
		vector<unsigned char>::type	bits;
		
		const static unsigned char	bit_mask[8];	// = { 1, 2, 4, 8, 16, 32, 64, 128 };
		const static unsigned char	bit_count[16];	// = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
	};
	
    
	class _OgreExport ProgressiveMesh : public MemAlloc_Geometry
    {
    public:
		typedef vector<Real>::type LodValueList;
		
		
        enum VertexReductionQuota
		{
			/// A set number of vertices are removed at each reduction
			VRQ_CONSTANT,
			/// A proportion of the remaining number of vertices are removed at each reduction
			VRQ_PROPORTIONAL,
			/// All vertices with reduction error cost less than reductionValue * sqr(lodDistance[lodLevel] / lodDistance[0]) 
			/// are removed at each reduction. Error cost is calculated as introduced error area divided by squared mesh diagonal
			VRQ_ERROR_COST,
		};

		
		
		static bool generateLodLevels(Mesh* pMesh, const LodValueList& lodValues,
									  VertexReductionQuota reductionMethod, Real reductionValue);

		
		static MeshPtr generateSimplifiedMesh(const String& name, const String& groupName, Mesh* inMesh,
											  bool dropOriginalGeometry, const LodValueList& lodValues,
											  VertexReductionQuota reductionMethod, Real reductionValue,
											  size_t* removedVertexDuplicatesCount);
	protected:
		typedef vector<ProgressiveMesh*>::type ProgressiveMeshList;

		/// Allocates internal resources
		static void initializeProgressiveMeshList(ProgressiveMeshList& pmList, Mesh* pMesh);

		/// Deletes allocated internal resources.
		static void freeProgressiveMeshList(ProgressiveMeshList* pmList);

        
		ProgressiveMesh(SubMesh* pSubMesh);
        virtual ~ProgressiveMesh();

        
        virtual void addExtraVertexPositionBuffer(const VertexData* vertexData);

        
		static bool build(ProgressiveMeshList& pmInList,
						  const LodStrategy *lodStrategy, const LodValueList& lodValues,
						  VertexReductionQuota quota, Real reductionValue = 0.5f);
						
    protected:
		/// Can be NULL for non-indexed subMeshes, such PM would be skipped
		SubMesh* mSubMesh;
		
        VertexData *mVertexData;
        IndexData *mIndexData;

		vector<IndexData*>::type mLodFaceList;
		
		size_t mRemovedVertexDuplicatesCount;	
		size_t mCurrNumIndexes;
		float mInvSquaredBoundBoxDiagonal;
		int mVertexComponentFlags;	

        // Internal classes
        class PMTriangle;
        class PMVertex;
		struct vertexLess;

    public: // VC6 hack

        
		class _OgrePrivate PMFaceVertex {
		public:
			size_t realIndex;
			PMVertex* commonVertex;
		};

	protected:

        
        class _OgrePrivate PMTriangle {
        public:
            PMTriangle();
            void setDetails(size_t index, PMFaceVertex *v0, PMFaceVertex *v1, PMFaceVertex *v2);
	        void computeNormal(void);
	        void replaceVertex(PMFaceVertex *vold, PMFaceVertex *vnew);
	        bool hasCommonVertex(PMVertex *v) const;
	        bool hasFaceVertex(PMFaceVertex *v) const;
			PMFaceVertex* getFaceVertexFromCommon(PMVertex* commonVert);
	        void notifyRemoved(void);

	        PMFaceVertex*	vertex[3];	// the 3 points that make this tri
	        Vector3			normal;		// unit vector orthogonal to this face
			Real			area;
            bool			removed;	// true if this tri is now removed
			size_t			index;
        };

        
        class _OgrePrivate PMVertex {
        public:
			enum BorderStatus { BS_UNKNOWN = 0, BS_NOT_BORDER, BS_BORDER };
            typedef SmallVector<PMVertex *, 8> NeighborList;
	        typedef SmallVector<PMTriangle *, 8> FaceList;

		public:
            PMVertex() : mBorderStatus(BS_UNKNOWN), removed(false) {}

			void setDetails(size_t index, const Vector3& pos, const Vector3& normal, const Vector2& uv);
		
			bool isNearEnough(PMVertex* other) const;
	        void removeIfNonNeighbor(PMVertex *n);
			void initBorderStatus(void);/// Set mBorderStatus to BS_BORDER if this vertex is on the edge of an open geometry patch
			bool isManifoldEdgeWith(PMVertex* v); // is edge this->src a manifold edge?
			void notifyRemoved(void);
			void calculateNormal();
		
            Vector3 position;  // location of point in euclidean space
			Vector3 normal;
			Vector2 uv;
			
	        size_t index;       // place of vertex in original list

			BorderStatus mBorderStatus;			
            bool      removed;   // true if this vert is now removed
			bool	  toBeRemoved; // debug

	        Real collapseCost;  // cached cost of collapsing edge
	        PMVertex * collapseTo; // candidate vertex for collapse
			
            NeighborList neighbor; // adjacent vertices
            FaceList face;     // adjacent triangles
        };
		
        typedef vector<PMTriangle>::type TriangleList;
        typedef vector<PMFaceVertex>::type FaceVertexList;
        typedef vector<PMVertex>::type CommonVertexList;
		typedef std::pair<Real, unsigned int> CostIndexPair;
		typedef vector<CostIndexPair>::type WorstCostList;

        /// Data used to calculate the collapse costs
        struct PMWorkingData
        {
            TriangleList mTriList; /// List of faces
            FaceVertexList mFaceVertList; // The vertex details referenced by the triangles
			CommonVertexList mVertList; // The master list of common vertices
        };

        typedef vector<PMWorkingData>::type WorkingDataList;
        /// Multiple copies, 1 per vertex buffer
        WorkingDataList mWorkingData;

        /// The worst collapse cost from all vertex buffers for each vertex
        WorstCostList	mWorstCosts;		// sorted by cost, but some of entries are invalidated, so check invalidCostMask
		BitArray		mInvalidCostMask;	// indexed by vertex index
		size_t			mInvalidCostCount;
		size_t			mWorstCostsSize;
		size_t			mNextWorstCostHint;	// getNextCollapser() uses it to reduce complexity from O(n^2) to O(n)
			
		/// Temporary variable used in computeEdgeCollapseCost, declared here to avoid multiple memory allocations
		mutable PMVertex::FaceList mEdgeAdjacentSides;

        /// Internal method for building PMWorkingData from geometry data
        void addWorkingData(const VertexData* vertexData, const IndexData* indexData);
		void mergeWorkingDataBorders();
		
        /// Internal method for initialising the edge collapse costs
        void initialiseEdgeCollapseCosts(void);
        /// Internal calculation method for deriving a collapse cost  from u to v
        Real computeEdgeCollapseCost(PMVertex *src, PMVertex *dest) const;
        /// Internal calculation method, return true if edge collapse flip some neighbor face normal
        bool collapseInvertsNormals(PMVertex *src, PMVertex *dest) const;
        /// Internal method evaluates all collapse costs from this vertex and picks the lowest for a single buffer
        Real computeEdgeCostAtVertexForBuffer(PMVertex* v);
        /// Internal method evaluates all collapse costs from this vertex for every buffer and returns the worst
        Real computeEdgeCostAtVertex(size_t vertIndex);
        /// Internal method to compute edge collapse costs for all buffers /
        void computeAllCosts(void);

        /// Internal methods for lazy costs recomputing
		static size_t getInvalidCostCount(ProgressiveMesh::ProgressiveMeshList& pmList);
		static bool recomputeInvalidCosts(ProgressiveMeshList& pmInList);
		void recomputeInvalidCosts();
		void sortIndexesByCost();
		static int cmpByCost(const void* p1, const void* p2); // comparator for mWorstCosts sorting
		
        /// Internal methods for getting the index of next best vertex to collapse among all submeshes
		static void getNextCollapser(ProgressiveMeshList& pmList, ProgressiveMesh*& pm, CostIndexPair*& bestCollapser);
		CostIndexPair* getNextCollapser();
		
        /// Internal method builds an new LOD based on the current state
        void bakeNewLOD(IndexData* pData);
		/// Internal method builds an LODs usage, possibly skipping first LOD, that can be used as original geometry
		static void bakeLodUsage(Mesh* pMesh, LodStrategy *lodStrategy, const LodValueList& lodValues, bool skipFirstLodLevel = false);

        
        void collapse(PMVertex *collapser);

		/// We can defragment mesh, removing unused vertices and re-indexing other, storing old-to-new mapping in index map
		typedef std::pair<unsigned, PMVertex*> IndexVertexPair;
		/// Optionally discards first LOD level (i.e. original geometry), removes unused vertices, remaps indexes.
		static void bakeSimplifiedMesh(Mesh* destMesh, Mesh* srcMesh, ProgressiveMeshList& pmList, bool dropFirstLodLevel = false);
		/// Defragments vertices, removing unused. Useful if original geometry is redundant or dropped at all.
		static void	createSimplifiedVertexData(vector<IndexVertexPair>::type& usedVertices, VertexData* inVData, VertexData*& outVData, AxisAlignedBox& aabox);
		/// During vertices defragmentation vertices are re-indexed, so old-to-new mapping is stored in index map by this function.
		static void createIndexMap(vector<IndexVertexPair>::type& usedVertices, unsigned allVertexCount, vector<unsigned>::type& indexMap);
		
		
		void dumpContents(const String& log);
    };
			
	template <typename T> struct HardwareBufferLockGuard
	{
		HardwareBufferLockGuard(const T& p, HardwareBuffer::LockOptions options)
		: pBuf(p)
		{
			pData = pBuf->lock(options);
		}
		HardwareBufferLockGuard(const T& p, size_t offset, size_t length, HardwareBuffer::LockOptions options)
		: pBuf(p)
		{
			pData = pBuf->lock(offset, length, options);
		}		
		~HardwareBufferLockGuard()
		{
			pBuf->unlock();
		}
		const T& pBuf;
		void* pData;
	};
	
	typedef HardwareBufferLockGuard<HardwareVertexBufferSharedPtr> VertexBufferLockGuard;
	typedef HardwareBufferLockGuard<HardwareIndexBufferSharedPtr> IndexBufferLockGuard;
	
	
	
}

#endif 
